// @algorithm @lc id=100328 lang=cpp
// @title fan-zhuan-dan-ci-shun-xu-lcof

#include "algm/algm.h"
#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int startPos = 0, endPos = 0;
        stack<string> helpStack;
        bool isValid = false;
        while (startPos < n && endPos < n) {
            // 遇到无效空格
            if (startPos == endPos && s[startPos] == ' ') {
                ++startPos;
                ++endPos;
            }
            // 遇到单词起点
            else if (startPos == endPos && s[startPos] != ' ') {
                isValid = true;
                if (endPos != n - 1) {
                    ++endPos;
                }
            }
            // 单词扩展
            else if (s[endPos] != ' ') {
                ++endPos;
            }
            // 遇到单词结尾后的空格
            if (s[endPos] == ' ' && isValid) {
                helpStack.push(s.substr(startPos, endPos - startPos));
                isValid = false;
                ++endPos;
                startPos = endPos;
            }
            // 遇到字符串结束
            if (endPos == n - 1 && isValid) {
                helpStack.push(s.substr(startPos, endPos - startPos + 1));
                ++endPos;
            }
        }
        string ans;
        while (!helpStack.empty()) {
            ans += helpStack.top();
            helpStack.pop();
            ans += " ";
        }
        if (!ans.empty()) {
            ans.pop_back();
        }
        return ans;
    }
};
